#include <cstdlib>
#include <cstdio>

/**
 * 字串：串中任意个连续字符组成的子序列
 * ch字符数组
 * length 字符串当前长度
*/
#define MAXLENGTH 255
typedef struct String{
	char ch[MAXLENGTH];
	int length = 0;
} String;

/**
 * 打印字符串
 * @param s
 */
void print(String s) {
	for (int i = 0; i < s.length; i++) {
		printf("%c", s.ch[i]);
	}
	printf("\n");
}

/**
 * 指定一个字符串
 * @param T
 * @param chars
 * @param length
 */
void Assign(String &T, char chars[], int length) {
	// 循环遍历赋值
	for (int i = 0; i < length; i++) {
		T.ch[i] = chars[i];
	}
	// 字符串长度
	T.length = length;
}

/**
 * 获取字符串长度
 * @param s 字符串
 * @return
 */
int length(String s) {
	return s.length;
}

/**
 * 截取字符串（包头不包尾）
 * @param s 源字符串
 * @param start 开始下标
 * @param end 结束下标（最终结果不包含结束下标对应元素）
 * @return 截取后的字符串
 */
String subStr(String s, int start, int end) {
	// 声明一个字符串结构体
	String returnStr;
	// 开始和结束下标的合法检验
	if (start < 0 || end < 0 || start > end) {
		return returnStr;
	}
	// 新字符串的长度
	returnStr.length = end - start;
	// 新字符串赋值
	for (int i = 0; i < returnStr.length; i++) {
		returnStr.ch[i] = s.ch[start + i];
	}
	return returnStr;
}

/**
 * 字符串对比
 * @param s1
 * @param s2
 * @return s1 > s2 结果大于0 s1 < s2 结果小于0 s1 = s2 结果等于0
 */
int compare(String s1, String s2) {
	for (int i = 0; i < s1.length && i < s2.length; i++) {
		// 根据字符的ASCII码标进行比较， 两字符ASCII码相等则继续
		if (s1.ch[i] != s2.ch[i]) {
			// 不相等返回当前两个字符的差
			return s1.ch[i] - s2.ch[i];
		}
	}
	// 当循环结束时没有得出结果有两种情况
	// 1、长度不相等但循环中对比的字符全部一样，用两者长度差作为结果，差为正数则 s1 > s2 差为负数则 s1 < s2
	// 2、长度一样两且内容一样长度相减为0结果相等
	return s1.length - s2.length;
}

/**
 * 子串在源字符串中的位置
 * @param s 源字符串
 * @param sub 子串
 * @return 若源字符串中包含子串返回字串在源字符串中地一次出现的位置的第一个字符的下标，若元字符串中不包含子串返回-1
 */
int index(String s, String sub) {
	// 声明临时字符串变量
	String temp;
	// 循环截取源字符串与子串进行对比
	for (int i = 0; i < s.length - sub.length + 1; i++) {
		// 在源字符串中截取与子串相同长度的临时子串
		temp = subStr(s, i, sub.length + i);
		// 根据上面的对比函数结果判断子串是否出现在源字符串，如果有那么返回第一次出现子串的开头字符的下标
		if (compare(temp, sub) != 0) {
			continue;
		} else {
			return i;
		}
	}
	return -1;
}

/**
 * 朴素模式匹配算法
 * @param s 源字符串
 * @param sub 子串
 * @return 若源字符串中包含子串返回字串在源字符串中地一次出现的位置的第一个字符的下标，若元字符串中不包含子串返回-1
 */
int index1(String s, String sub) {
	int i = 0;
	int j = 0;
	while(i < s.length && j < sub.length) {
		// 当前字符相同则将循环指针统一后移
		if (s.ch[i] == sub.ch[j]) {
			i++;
			j++;
		} else {
			// 当前字符不同将子串的循环指针重置，源字符串的循环指针置后移一位
			i = i - j + 1;
			j = 0;
		}
	}
	// 因为当最后一次执行循环的时候j的最大值是子串长度+1，所以循环完成后j的值大于子串的最后一个字符的下标的值时
	// 证明子串在源字符串中出现过，由于已经对比到子串的最后一个字符所以第子串第一个字符的下表就是此时的i减去字串长度
	if (j > sub.length - 1) {
		return i - sub.length;
	}
	return -1;
}

/**
 * kmp算法的next数组计算
 * @param s 字符串
 * @param next next数组
 */
void getNext(String s, int next[]) {
	// 记录需要回溯的位置
	int j = 0;
	// next数组的第一个元素初始化为0，因为当第一个字符都不匹配是回溯位置是0
	next[0] = 0;
	// 因为第一个字符不匹配已知所以从第二个字符开始
	for (int i = 1; i < s.length; i++) {
		// 如果当前字符匹配则将回溯位置+1
		if (s.ch[i] == s.ch[j]) {
			j++;
		}
		// 如果当前字符不匹配则将回溯直到子串j位置之前和源字符串i位置之前的能够匹配，或者全部不匹配
		while (j > 0 && s.ch[i] != s.ch[j]) {
			j = next[j - 1];
		}
		// j的最终结果就是每个字符需要回溯的位置
		next[i] = j;
	}
}

int kmp(String s, String sub) {
	// 生命next数组
	int next[sub.length];
	// 根据子串获取next数组
	getNext(sub, next);
	// next数组的指针变量
	int j = 0;
	for (int i = 0; i < s.length; i++) {
		// 不匹配就回溯
		while (j > 0 && s.ch[i] != sub.ch[j]) {
			j = next[j - 1];
		}
		// 匹配就让next数组指针后移
		if (s.ch[i] == sub.ch[j]) {
			j++;
		}
		// 由于j是数组的指针变量且从零开始，同时next数组的长度于子串长度相同
		// 所以当最后一次匹配成功j++的时候j的值就和子串的长度相等，也就意味这在源字符串中有与子串匹配的字符串
		if (j == sub.length) {
			// 所匹配的字符串的第一个元素下标在源字符串中的位置是：
			// 当前i指向的是匹配字符串的最后一个字符，那么第一个字符的下标就是i减去子串长度加1
			return i - sub.length + 1;
		}
	}
	return -1;
}



//       j	0	1	2	3	4	5	6	7	8	9	10
//     子串	h	e	l	l	o	,	w	o	r	l	d
// next[j]	0	1	1	1	1	1	1


//       j	0	1	2	3	4	5
//       i		1	2	3	4	5
//     子串	a	b	a	b	a	a
// next[j]	0	1